package library;

import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * Plain and simple, Dijkstra's algorithm
 * @author ekulcyk
 *
 */
public class Dijkstra {
	
	public double dijkstra(Node start, Node end, List<Node> nodes){
		PriorityQueue<Node> pq = new PriorityQueue<Node>();
		
		start.distance=0;
		pq.add(start);
		
		for (Node n : nodes)
			if (n!=start)
				n.distance=Integer.MAX_VALUE;
		
		while (!pq.isEmpty()){
			Node current = pq.poll();
			for (Edge e : current.edges)
				if (current.distance+e.length<e.end.distance){
					e.end.distance=current.distance+e.length;
					pq.remove(e.end);
					pq.add(e.end);
				}
		}
		return end.distance;
	}
	class Node implements Comparable<Node>{
		double distance;
		List<Edge> edges;
		public Node(){
			edges = new LinkedList<Edge>();
			distance = Integer.MAX_VALUE;
		}
		@Override
		public int compareTo(Node o) {
			if (o.distance - distance >1e-6)
				return -1;
			else if (distance == o.distance)
				return 0;
			else
				return 1;
		}
	}
	class Edge{
		Node end;
		double length;
		
		public Edge(Node end, double length){
			this.end=end;
			this.length=length;
		}
	}
}
